/**
 * 33. Search in rotated sorted array
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 */
class SearchInRotatedSortedArray {
    /**
     * 方法：二分查找
     * 在旋转排序数组中查找目标值。通过比较中间元素与最后一个元素的大小关系来判断目标值在哪一侧。
     * 如果中间元素大于最后一个元素，说明该元素在旋转点左侧；否则在右侧。
     * 然后根据目标值与最后一个元素的大小关系，判断目标值应该在哪一
     * Args:
     *     nums: List[int], 旋转排序数组
     *     target: int, 要查找的目
     * Returns:
     *     int: 如果找到目标值返回其索引，否则返回
     * Time: O(logn)，其中n是数组的长度，每次将搜索范围缩小
     * Space: O(1)，只使用常数额外空间
     */
    public int search(int[] nums, int target) {
        int left = -1;
        int right = nums.length - 1;
        while (left + 1 < right){
            int mid = (left + right) >>> 1;
            if(check(nums, target, mid)){
                right = mid;
            }else{
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

    public boolean check(int[] nums, int target, int i){
        int x = nums[i];
        int end = nums[nums.length -1];
        if(x > end){
            return target > end && x >= target;
        }
        return target > end || x >= target;
    }
}